package demo.practice.competition;

import java.util.LinkedList;
import java.util.Queue;


public class P5793_3 {


    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;

        int[][] locations = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};  //4个方向
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{entrance[0], entrance[1], 0});
        maze[entrance[0]][entrance[1]] = '+';

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int cx = poll[0];
            int cy = poll[1];
            int d = poll[2];

            for (int[] xy : locations) {
                int nx = cx + xy[0];
                int ny = cy + xy[1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.') {
                    if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {
                        // 新坐标为出口，返回距离作为答案
                        return d + 1;
                    }
                    maze[nx][ny] = '+';
                    q.add(new int[]{nx, ny, d + 1});
                }
            }
        }
        return -1;
    }
}
